package com.leetcode.根据算法进行分类.双指针相关;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author: ZhouBert
 * @date: 2021/2/4
 * @description: 42. 接雨水
 * https://leetcode-cn.com/problems/trapping-rain-water/
 */
public class C_42_接雨水 {

    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        height = new int[]{4, 2, 0, 3, 2, 5};
        C_42_接雨水 action = new C_42_接雨水();
        //int res = action.trap(height);
        int res = action.trapByForce(height);
        System.out.println("res = " + res);
    }

    /**
     * 1.遍历一遍，将元素放入大顶堆中；
     * 2.跟左右边界还是有关系的，所以仍然还是个双指针的问题。
     * --
     * 优化:
     * 1.当 len <3 时，可以直接返回0.
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int len = height.length;
        int res = 0;
        if (len == 0 || len == 1) {
            return res;
        }
        PriorityQueue<Peak> heap = new PriorityQueue<>(new Comparator<Peak>() {
            @Override
            public int compare(Peak o1, Peak o2) {
                return o2.value - o1.value;
            }
        });
        for (int i = 0; i < len; i++) {
            heap.offer(new Peak(i, height[i]));
        }

        //借助一个集合存放 index
        //HashSet<Integer> set = new HashSet<>();
        Peak firstPeak = heap.poll();
        Peak secondPeak = heap.poll();
        Peak left, right, curPeak;
        //1.赋值左右边界
        if (firstPeak.index < secondPeak.index) {
            left = firstPeak;
            right = secondPeak;
        } else {
            left = secondPeak;
            right = firstPeak;
        }
        res += countPeak(left, right, height);
        int endIndex = len - 1;
        while (!heap.isEmpty()) {
            if (right.index - left.index == endIndex) {
                break;
            }
            //2.重新弹出堆顶元素
            curPeak = heap.poll();
            if (curPeak.index < left.index) {
                res += countPeak(curPeak, left, height);
                left = curPeak;
            } else if (curPeak.index > right.index) {
                res += countPeak(right, curPeak, height);
                right = curPeak;
            }
        }

        return res;
    }

    /**
     * 计算 peak 之间的水的洼地
     *
     * @param left
     * @param right
     * @param height
     * @return
     */
    private int countPeak(Peak left, Peak right, int[] height) {
        int min = Math.min(height[left.index], height[right.index]);
        int res = (right.index - left.index - 1) * min;
        for (int i = left.index + 1; i < right.index; i++) {
            res -= height[i];
        }
        return res;
    }


    /**
     * 步骤：
     * 每一个洼地都有两个边界。
     * 由于非负，所以不用考虑负数的影响
     * 1.找到第一个 上升序列的峰值（即左边界），
     * 2.
     * --
     * 我的想法是错的。不能直接使用上升和下降来判断边界
     *
     * @param height
     * @return
     */
    public int trapFail(int[] height) {
        int len = height.length;
        int res = 0;
        if (len == 0) {
            return res;
        }
        int begin = 0, end = 1;
        int lowIndex = 0;
        while (end < len && height[begin] <= height[begin + 1]) {
            //如果处于上升
            begin++;
            end++;
        }
        int endIndex = len - 1;
        while (end < len) {

            lowIndex = end++;
            //此时 begin 处于最高峰，并且必定下坡
            //接下来寻找 end -- 第二个最高峰，之前需要找到低谷
            while (end < len && height[lowIndex] >= height[lowIndex + 1]) {
                lowIndex++;
                end++;
            }
            //此时 lowIndex 处于最低谷，并且接下来必定上坡
            //接下来寻找 end
            while (end < endIndex && height[end] <= height[end + 1]) {
                //如果处于上升
                end++;
            }
            if (end == len) {
                break;
            }
            res += count(begin, end, height, len);
            begin = end;
            end = begin + 1;
        }
        return res;
    }

    /**
     * 通过暴力解法解决
     * 1.计算每一个索引位置的雨水值；
     * 2.上值是通过 Math.min(leftMax, rightMax) 求得：
     * 如果该值 <= height(index) 就说明不会生成洼地，就不用处理；反之加入到结果当中
     * --
     * 暴力解法的思路确实很清晰
     *
     * @param height
     * @return
     */
    public int trapByForce(int[] height) {
        //1.初步判断
        int len = height.length;
        int res = 0;
        if (len < 3) {
            return res;
        }
        int endIndex = len - 1;
        int leftMax = 0, rightMax = 0;
        for (int i = 1; i < endIndex; i++) {
            leftMax = getLeftMax(i, height);
            rightMax = getRightMax(i, height);
            int temp = Math.min(leftMax, rightMax);
            if (temp > height[i]) {
                //如果小于此处的值，就不会生成洼地
                res += temp - height[i];
            }

        }
        return res;
    }

    /**
     * 获取 index 位置右边的 max 不包括 index
     *
     * @param index
     * @param height
     * @return
     */
    private int getLeftMax(int index, int[] height) {
        int res = height[0];
        for (int i = 1; i < index; i++) {
            res = Math.max(res, height[i]);
        }
        return res;
    }

    /**
     * 获取 index 位置左边的 max 不包括 index
     *
     * @param index
     * @param height
     * @return
     */
    private int getRightMax(int index, int[] height) {
        int endIndex = height.length - 1;
        int res = height[endIndex];
        for (int i = endIndex; i > index; i--) {
            res = Math.max(res, height[i]);
        }
        return res;

    }

    /**
     * 通过动态规划对 暴力解法进行优化！
     * 由于求 leftMax 和 rightMax 是一个量变到巨变的过程！
     * dpLeftMax[i]=Math.max(dpLeftMax[i-1],height[i])
     * 同理：
     * dpRightMax[i]=Math.max(dpRightMax[i+1],height[i])
     * --
     * 使用了 dp 可以优化到 打败 50%
     * @param height
     * @return
     */
    public int trapByDynamicProgramming(int[] height) {
        //1.初步判断
        int len = height.length;
        int res = 0;
        if (len < 3) {
            return res;
        }

        int[] dpLeftMax = new int[len];
        dpLeftMax[0] = height[0];
        int[] dpRightMax = new int[len];
        int endIndex = len - 1;
        dpRightMax[endIndex] = height[endIndex];
        for (int i = 1; i < len; i++) {
            dpLeftMax[i] = Math.max(dpLeftMax[i - 1], height[i]);
        }
        for (int i = endIndex - 1; i > -1; i--) {
            dpRightMax[i]=Math.max(dpRightMax[i+1], height[i]);
        }
        //然后再套上暴力解法的框架即可
        // （使用 dp 是典型的用空间换时间的行为，将过程储存起来，避免了重复的计算！）
        int leftMax = 0, rightMax = 0;
        for (int i = 1; i < endIndex; i++) {
            leftMax = dpLeftMax[i];
            rightMax = dpRightMax[i];
            int temp = Math.min(leftMax, rightMax);
            if (temp > height[i]) {
                //如果小于此处的值，就不会生成洼地
                res += temp - height[i];
            }

        }
        return res;
    }


    /**
     * 计算 begin ~ end 之间的水量
     *
     * @param begin
     * @param end
     * @param height
     * @param len
     * @return
     */
    private int count(int begin, int end, int[] height, int len) {
        int min = Math.min(height[begin], height[end]);
        int res = (end - begin - 1) * min;
        for (int i = begin + 1; i < end; i++) {
            res -= height[i];
        }
        return res;
    }

    static class Peak {
        int index;
        int value;

        public Peak(int index, int value) {
            this.index = index;
            this.value = value;
        }
    }
}
